﻿/* * Write a program that reads a number N and generates and prints all the permutations of the numbers [1 … N]. Example:
	n = 3  {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}
*/




using System;

class Permutations
{
    static void Main()
    {
        bool iProvided = false;
        int N;
        do
        {
            if (iProvided == true) Console.WriteLine("Error occurred. Please enter an integer.");
            else iProvided = true;
            Console.Write("Enter N: ");
        } while (Int32.TryParse(Console.ReadLine(), out N) == false);

        int[] arr = new int[N];
        bool[] used = new bool[arr.Length];
        string results = Permutations_(arr, used, 0);
        Console.WriteLine(results);
    }

    private static string Permutations_(int[] arr, bool[] used, int p)
    {
        string res = null;
        if (p == arr.Length)
        {
            res = Check(arr);
            return null;
        }

        for (int j = 0; j < arr.Length; j++)
        {
            if (used[j]) continue;

            arr[p] = j;

            used[j] = true;
            res = Permutations_(arr, used, p + 1);
            used[j] = false;
        }
        return res;
    }

    private static string Check(int[] arr)
    {
        string res = null;
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i] + 1 + (i == arr.Length - 1 ? "\n" : " "));
            if (i == arr.Length - 1) res = "\n";
            else res = " ";
            Console.Write(res);
        }
        //return res;
        return null;
    }
}
